package com.example.myapplication9.week4.jsjf;



import com.example.myapplication9.week4.jsjf.exceptions.ElementNotFoundException;
import com.example.myapplication9.week4.jsjf.exceptions.EmptyCollectionException;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 链表实现列表
 * 
 * @author Lewis and Chase
 * @version 4.0
 */
public class LinkedList<T> implements ListADT<T>, Iterable<T>
{
    protected int count;
    protected LinearNode<T> head, tail;
	protected int modCount;
    
    /**
     * 创建一个空列表.
     */
    public LinkedList()
    {
        count = 0;
        head = tail = null;
		modCount = 0;
	}
   
    /**
     * 删除列表的第一个元素并返回一个他的引用，如果列表为空，则抛出EmptyCollectionException；.
     *
     * @return 列表第一个元素的引用
     * @throws EmptyCollectionException 如果列表为空
     */
    @Override
    public T removeFirst() throws EmptyCollectionException
    {
        if(isEmpty())
            throw new EmptyCollectionException("LinkedList");

        LinearNode <T> list=head;
        if(size()==1)
        {
            head=tail=null;

        }
        else {
            head=head.getNext();
        }
        count--;
        return  list.getElement();
    }
   
    /**
     *  删除列表的最后一个元素并返回他.，抛出EmptyCollectionException如果列表为空
     * @return 返回列表的最后一个元素
     * @throws EmptyCollectionException 如果列表为空
     */
    @Override
    public T removeLast() throws EmptyCollectionException
    {
              if(isEmpty())
                  throw new EmptyCollectionException("LinkedList");

              LinearNode<T> list=tail;
              if(size()==1)
                  head=tail=null;
              else
              {
                  LinearNode list1=head;
                  while(list1.getNext().getNext()!=null)
                  {
                      list1=list1.getNext();
                  }
                  tail=list1;
                  tail.setNext(null);

              }
              count--;
              return list.getElement();
    }
   
    /**
     * 移除列表中被指定的元素的第一个搜索对象，当列表为空时，抛出EmptyCollectionException.，找不到指定元素时，则抛出ElementNotFoundException。
     * @param  targetElement 值得是要从连表中删除的哪一个元素
     * @return 返回被删除的那个元素的引用
     * @throws EmptyCollectionException 如果列表为空
	 * @throws ElementNotFoundException 如果目标元素没有被找到
     */
    @Override
    public T remove(T targetElement) throws EmptyCollectionException,
            ElementNotFoundException
    {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");
      
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;
      
        while (current != null && !found)
            if (targetElement.equals(current.getElement()))
                found = true;
            else {
                previous = current;
                current = current.getNext();
            }

        if (!found)
            throw new ElementNotFoundException("LinkedList");
      
        if (size() == 1)  // 列表中只有一个元素
            head = tail = null;
        else if (current.equals(head))  // 目标在头部
            head = current.getNext();
        else if (current.equals(tail))  // 目标在尾部
        {
            tail = previous;
            tail.setNext(null);
        }
        else  // 目标在中间
            previous.setNext(current.getNext());
      
        count--;
		modCount++;
      
        return current.getElement();
    }
   
    /**
     * 只返回列表中的第一个元素而不删除他.
     *
     * @return 列表的第一个元素
	 * @throws EmptyCollectionException 如果列表为空。
     */
    @Override
    public T first() throws EmptyCollectionException
    {
        if(isEmpty())
            throw new EmptyCollectionException("LinkedList");

        return head.getElement();
    }
	
    /**
     * 不删除并返回列表的最后一个元素。
     *
     * @return 列表中的最后一个元素
	 * @throws EmptyCollectionException 如果列表为空
     */
    @Override
    public T last() throws EmptyCollectionException
    {
       if(isEmpty())
           throw new EmptyCollectionException("LinkedList");

        return tail.getElement();
    }
	
    /**
     * 返回真如果元素被找到，否则返回假，如果列表为空则抛出EmptyCollectionException
     *
     * @param  targetElement 列表中被搜索的元素。
     * @return 真如果元素在列表中被找到
     * @throws EmptyCollectionException 如果列表为空
     */
    @Override
    public boolean contains(T targetElement) {
        boolean idea = false ;
        if (head==null)
            throw new EmptyCollectionException("LindedList");
        else{
            if (count == 1)
                idea=(head.getElement()==targetElement);
            else {
                LinearNode<T> current1 = head;
                LinearNode<T> list  = head.getNext();
                if (current1.getElement() == targetElement)
                    idea = true;
                else{
                    while(list.getElement()!=targetElement&&list.getNext()!=null)
                    { list =list.getNext(); }
                    if (list.getElement()==targetElement)
                        idea =true;
                }
            }
        }
        return idea;
    }
   
    /**
     * 如果列表为空则返回真如果列表哦不为空则返回假.
     *
     * @return 列表为空返回真，不为空返回假。
     */
    @Override
    public boolean isEmpty()
    {
        if(count==0)
            return true;
        else
            return false;
    }

    /**
     * 返回列表中元素的数量.
     *
     * @return 列表中元素的数量
     */
    @Override
    public int size()
    {
        return count;
    }

    /**
     * 返回列表的一个字符串类型的展示
     *
     * @return 列表的字符串类型的展示
     */
    @Override
    public String toString()
    {
        LinearNode<T>list=head;
         String result=""+list.getElement()+" ";

        while(list.getNext()!=null)
        {
            list=list.getNext();
            result+=list.getElement()+" ";
        }
        return result;
    }

    /**
     * Returns an iterator for the elements in this list. 
     *
     * @return an iterator over the elements of the list
     */

    @Override
    public Iterator<T> iterator()
    {
        return new LinkedListIterator();
    }

	/**
	 * LinkedIterator represents an iterator for Translation linked list of linear nodes.
	 */
	private class LinkedListIterator implements Iterator<T>
	{
		private int iteratorModCount;  // the number of elements in the collection
		private LinearNode<T> current;  // the current position

		public LinkedListIterator()
		{
			current = head;
			iteratorModCount = modCount;
		}
		
		/**
		 * Returns true if this iterator has at least one more element
		 * to deliver in the iteration.
		 *
		 * @return  true if this iterator has at least one more element to deliver
		 *          in the iteration
		 * @throws  ConcurrentModificationException if the collection has changed
		 *          while the iterator is in use
		 */
		@Override
        public boolean hasNext() throws ConcurrentModificationException
		{
			if (iteratorModCount != modCount) 
				throw new ConcurrentModificationException();
			
			return (current != null);
		}
		
		/**
		 * Returns the next element in the iteration. If there are no
		 * more elements in this iteration, Translation NoSuchElementException is
		 * thrown.
		 *
		 * @return the next element in the iteration
		 * @throws NoSuchElementException if the iterator is empty
		 */
		@Override
        public T next() throws ConcurrentModificationException
		{
			if (!hasNext())
				throw new NoSuchElementException();
			
			T result = current.getElement();
			current = current.getNext();
			return result;
		}
		
		/**
		 * The remove operation is not supported.
		 * 
		 * @throws UnsupportedOperationException if the remove operation is called
		 */
		@Override
        public void remove() throws UnsupportedOperationException
		{
			throw new UnsupportedOperationException();
		}
	}
	
}


